package service;

import gold.utils.InputUtil;

public class SearchLoopService {


    /**
     * 判断无向图是否存在环？
     * n表示输入数组的长度，数组里每个数字都小于n。 (n<=10000)
     * 1--2–3
     *    | |
     *    5–4
     * 如上图，2-3-4-5是一个环
     * <p>
     * 解题思路：
     * 1.for循环遍历edges，构建临接点map
     * 2.dfs 遍历map，查找环，已遍历的点用visited存储
     */

    public int N = 0;//总节点个数

    public String removeOneConnection(int[][] edges) {
        //先获取N，节省空间
        for (int[] edge : edges) {
            int start = edge[0], end = edge[1];
            N = Math.max(N, end);//因为描述里，end已经确保比start大
        }

        boolean[] visited = new boolean[N + 1];
        boolean[][] map = new boolean[N + 1][N + 1];

        for (int[] edge : edges) {
            int start = edge[0], end = edge[1];
            map[start][end] = true;
            map[end][start] = true; //双向图
        }

        for (int i = 1; i < N + 1; i++) {
            visited[i] = true;
            if (dfs(map, visited, i, 0)) return "Y";
            visited[i] = false;
        }

        return "N";
    }

    public boolean dfs(boolean[][] map, boolean[] visited, int cur, int pre) {
        for (int i = 1; i < N + 1; i++) {
            if (pre == i || cur == i || !map[cur][i]) continue;
            if (pre != i && cur != i && visited[i]) return true; //已经遍历过，认为出现环
            visited[i] = true;
            if (dfs(map, visited, i, cur)) return true;
            visited[i] = false;
        }
        return false;
    }

    public static void main(String[] args) {
        SearchLoopService an = new SearchLoopService();
        int[][] edges = InputUtil.toDoubleIntegerArray("[[1,2],[2,3],[3,4],[4,5],[2,5]]");
        System.out.println(an.removeOneConnection(edges));
    }

}
